"""
Functions for mapping structures to devices.
"""

import sys
from logger import logger

class MapperError(Exception):
    """
    handling class for mapper exceptions
    """
    
    def __init__(self, msg):
        """
        initialize the class
        """
        logger.error("mapper: %s" % msg)

def map(device_cellfield, system, avoid_faults, order_by_size, rotate):
    """
    map the structures of a system to the device

    @param device_cellfield: the device we want to map to
    @type device_cellfield: matrix of cells (list of lists)
    @param system: the set of structures to map to the device
    @type system: list
    @param avoid_faults: flag to avoid faults
    @type avoid_faults: boolean
    @param order_by_size: flag to map the largest structures first
    @type order_by_size: boolean
    @param rotate: flag to try rotating structures that don't fit
    @type rotate: boolean    

    @return: the resulting cellfield and a success boolean
    @rtype: tuple
    """
   
    old_cellfield = device_cellfield
    
    d_w = len(device_cellfield[0])
    d_h = len(device_cellfield)

    #get a list of the structure names
    struct_names = system.struct_dict.keys()

    #if using the sizeaware algorithm, sort
    if order_by_size:
        struct_names.sort(lambda x, y: system.struct_dict[y].area - system.struct_dict[x].area)
    
    #map each structure in the given system
    for name in struct_names:

        #get the structure by name
        struct = system.struct_dict[name]

        #determine the width and height of the structure to be mapped
        s_w = len(struct.cellfield[0])
        s_h = len(struct.cellfield)

        #find free space
        try:
            [x, y] = find_footprint(device_cellfield, avoid_faults, 
                                    d_h, d_w, 
                                    s_h, s_w)

        except MapperError: #if the structure can't be mapped
            if rotate:
                #rotate the structure
                rotated_cellfield = rotate_cellfield(struct.cellfield)
                s_w = len(rotated_cellfield[0])
                s_h = len(rotated_cellfield)
                #attempt to find a new footprint
                try: 
                    [x, y] = find_footprint(device_cellfield, avoid_faults, 
                                            d_h, d_w, 
                                            s_h, s_w)
                    
                    #rotated mapping was a success
                    struct.cellfield = rotated_cellfield
                except MapperError:
                    #that didn't work either
                    return (old_cellfield, False)
            else:
                #return the old cellfield
                return (old_cellfield, False)
            
        #set the cells
        device_cellfield = set_cells(x, y, 
                                     device_cellfield, struct.cellfield, 
                                     s_h, s_w)
        if device_cellfield == 0:
            return (old_cellfield, False)

    #return the new cell field
    return (device_cellfield, True)
    
def find_footprint(device_cellfield, avoid_faults, d_h, d_w, s_h, s_w):
    """
    find enough free space on the device for the structure's 'footprint'
    
    @param device_cellfield: the cellfield of the device we want to check
    @type device_cellfield: matrix of cells
    @param d_h: the height of the device cellfield
    @type d_h: int
    @param d_w: the width of the device cellfield
    @type d_w: int
    @param s_h: the height of the structure we want to map
    @type s_h: int
    @param s_w: the width of the structure we want to map
    @type s_w: int
    
    @return: the top coordinates of the top-left cell in this footprint
        if no adequate footprint is found, return [-1, -1]
    @rtype: list of two coordinates
    """  
    
    #iterate through the possible top-left cells
    for row in range(d_h - s_h + 1):
        for col in range(d_w - s_w + 1):
            if test_footprint(row, col, 
                              device_cellfield, avoid_faults, 
                              s_h, s_w):
                return [row, col]

    #no suitable mapping
    raise MapperError('no suitable mapping')
    
def test_footprint(row, col, device_cellfield, avoid_faults, s_h, s_w):
    """
    test a proposed footprint
    
    @param row: top row of the proposed footprint
    @param col: the left col of the proposed footprint
    @param device_cellfield: the cellfield to test
    @param s_h: the height of the structure we want to map to the propose footprint
    @param s_w: the width of the structure we want to map to the proposed footprint

    @return: true if all cells are free and functional, false if any cells are in use or faulty
    """
    #test each cell in the proposed footprint
    for x in range(s_h):
        for y in range(s_w):
            #get the cell type
            cell_type = device_cellfield[row + x][col + y].get_type()
            #TODO test this out
            #if we're looking for open and functional cells
            if avoid_faults:
                #the cell must be open and functional
                if cell_type != 'O': return False
            else:
                #otherwise, nonfunctional cell are fair game
                if cell_type != 'O' and  cell_type != 'F': return False
    #the footprint is good
    return True
    
def set_cells(row, col, d_cells, s_cells, s_h, s_w):
    """
    map a structure to a device, given the top left coordinate to start from
    
    @param row: the top row of the mapping destination in the device
    @param col: the left column of the mapping destination in the device
    @param d_cells: the target device cellfield
    @param s_cells: cellfield of the structure to be mapped to the device
    @param s_h: the height of the structure to be mapped
    @param s_w: the width of the structure to be mapped
    
    @return: the modified cellfield, or 0 on failure
    """
    for x in range(s_h):
        for y in range(s_w):
            old_type = d_cells[row + x][col + y].get_type()
            if old_type != 'F':
                new_type = s_cells[x][y].get_type()
                d_cells[row + x][col + y].set_type(new_type)
            else:
                raise MapperError('cannot write to failed cells')

    return d_cells

def rotate_cellfield(cellfield):
    """
    return a copy of the structure, rotated 90 degrees

    @param cellfield: the structure to be rotated
    @type cellfield: matrix of cells (list of lists)
    
    @return: the rotated copy of the structure
    @rtype: matrix of cells (list of lists)
    """
    rotated_cellfield = []
    line = []
    rows = len(cellfield)
    cols = len(cellfield[0])

    for col in range(cols):
        for row in reversed(range(rows)):
            line.append(cellfield[row][col])
        rotated_cellfield.append(line)
        line = []
    
    return rotated_cellfield
